package 排序算法.归并排序;

import java.util.Arrays;

/**
 * @Project: data-structure-and-algorithms
 * @Package: 排序.归并排序
 * @ClassName: MergeSort
 * @Author: zhouyihe
 * @Date: 2025/11/12 09:49
 * @Description: 归并排序
 */
public class MergeSort {
    private static int INSERTION_SORT_THRESHOLD = 10;

    public static void main(String[] args) {
        int[] arr = new int[]{4, 5, 2, 1, 6, 3};
        mergeSort(arr, 0, arr.length - 1);
        System.out.println(Arrays.toString(arr));
    }

    /***
     * 归并排序
     * 递归方法实现
     * 优点：
     * 时间复杂度稳定，在最好、最坏和平均情况下均为 O(nlogn)
     * 稳定排序算法，保持相等元素的相对顺序
     * 适合处理大规模数据，尤其是外部排序
     * 可以改造为并行算法，提高效率
     * 缺点：
     * 需要 O(n) 的额外空间
     * 对于小规模数据，递归开销较大
     * 不是原地排序算法，空间效率不如快速排序等
     * 在一些情况下，常数因子较大，实际性能可能不如快速排序
     * @param arr
     * @param left
     * @param right
     */

    private static void mergeSort(int[] arr, int left, int right) {
        // if (left >= right) {
        //     return;
        // }
        // 优化策略，当数组长度小于等于INSERTION_SORT_THRESHOLD时使用插入排序
        if (right - left <= INSERTION_SORT_THRESHOLD) {
            insertionSort(arr, left, right);
            return;
        }

        // 必须在右移处加括号，因为加号的优先级大于右移
        int mid = left + ((right - left) >> 1);
        mergeSort(arr, left, mid);
        mergeSort(arr, mid + 1, right);

        // 合并分区
        merge(arr, left, mid, right);

    }


    // 合并数组操作
    private static void merge(int[] arr, int left, int mid, int right) {
        // 如果arr[mid] <= arr[mid+1]，数组已经有序，无需合并
        if (arr[mid] <= arr[mid + 1]) {
            return;
        }

        int n1 = mid - left + 1;
        int n2 = right - mid;

        // 创建临时数组
        int[] temp1 = new int[n1];
        int[] temp2 = new int[n2];

        for (int i = 0; i < n1; i++) {
            temp1[i] = arr[left + i];
        }
        for (int i = 0; i < n2; i++) {
            temp2[i] = arr[mid + 1 + i];
        }

        // 合并临时数组
        int i = 0, j = 0, k = left;
        while (i < n1 && j < n2) {
            if (temp1[i] <= temp2[j]) {
                arr[k++] = temp1[i++];
            } else {
                arr[k++] = temp2[j++];
            }
        }

        while (i < n1) {
            arr[k++] = temp1[i++];
        }

        while (j < n2) {
            arr[k++] = temp2[j++];
        }

    }

    // 插入排序
    private static void insertionSort(int[] arr, int left, int right) {
        for (int i = left + 1; i <= right; i++) {
            int key = arr[i];
            int j = i - 1;

            while (j >= left && arr[j] > key) {
                arr[j + 1] = arr[j];
                j--;
            }

            arr[j + 1] = key;
        }
    }
}
